#include "common.h"

vector<vector<int>> threeSum(vector<int> nums)
{
	vector<vector<int>> v;
	sort(nums.begin(), nums.end());
	int k = nums.size() - 1;
	if (nums[0] > 0 || nums[nums.size() - 1] < 0)
		return v;
	while (k >= 2 && nums[k] >= 0)
	{
		int left = 0;
		int right = k - 1;
		while (left < right)
		{
			if (nums[left] + nums[right] == -nums[k])
			{
				vector<int> t({ nums[left], nums[right], nums[k] });
				v.push_back(t);
				left++;
				right--;
				while (left < right && nums[left - 1] == nums[left]) left++;
				while (left < right && nums[right + 1] == nums[right]) right++;
			}
			else if (nums[left] + nums[right] < -nums[k])
				left++;
			else
				right--;
		}
		k--;
		while (nums[k] == nums[k + 1] && k >= 2) k--;
	}
	return v;
}
